import heapq
from math import inf
from typing import List


class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        heap = [(0, start)]

        min_x, min_y = start
        max_x, max_y = target
        distances = [[inf for _ in range(max_y + 1)] for _ in range(max_x + 1)]
        visited = [[False for _ in range(max_y + 1)] for _ in range(max_x + 1)]
        distances[min_x][min_y] = 0
        while heap:
            curr_distance, (curr_x, curr_y) = heapq.heappop(heap)
            if visited[curr_x][curr_y]: continue
            visited[curr_x][curr_y] = True
            if curr_x == target[0] and curr_y == target[1]:
                return curr_distance
            for next_x, next_y in [(curr_x + 1, curr_y), (curr_x - 1, curr_y), (curr_x, curr_y + 1),
                                   (curr_x, curr_y - 1)]:
                if next_x < min_x or next_x > max_x: continue
                if next_y < min_y or next_y > max_y: continue
                if distances[curr_x][curr_y] + 1 < distances[next_x][next_y]:
                    distances[next_x][next_y] = distances[curr_x][curr_y] + 1
                    heapq.heappush(heap, (distances[next_x][next_y], (next_x, next_y)))
            for s_road in specialRoads:
                if curr_x == s_road[0] and curr_y == s_road[1]:
                    next_x, next_y = s_road[2], s_road[3]
                    dis = s_road[4]
                    if distances[curr_x][curr_y] + dis < distances[next_x][next_y]:
                        distances[next_x][next_y] = distances[curr_x][curr_y] + dis
                        heapq.heappush(heap, (distances[next_x][next_y], (next_x, next_y)))


if __name__ == '__main__':
    s = Solution()
    r = s.minimumCost(start=[1, 1], target=[4, 5], specialRoads=[[1, 2, 3, 3, 2], [3, 4, 4, 5, 1]])
    print(r)
